package com.lsa.letcode.the139.wordBreak;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
    	return canBeSegmented(prepare(s), dict, new HashMap<String, Boolean>());
//    	return canBeSegmentedDp(prepare(s), dict);
    	
    }
    
    private boolean canBeSegmentedDp(String s, Set<String> dict) {
    	boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
    	int len = s.length();
    	for (int l = 1; l <= len; l++) {
			for (int i = 0; i <= len - l; i++) {
				int j = l + i;
				boolean isCanBe = false;
				if (dict.contains(s.substring(i, j))) {
					isCanBe = true;
				}
				else {
					for (int k = i + 1; k < j; k++) {
						if (dp[i][k] && dp[k][j]) {
							isCanBe = true;
							break;
						}
					}
				}
				dp[i][j] = isCanBe;
			}
		}
    	return dp[0][s.length()];
    }

	private boolean canBeSegmented(String s, Set<String> dict, Map<String, Boolean> memo) {
		if (s == null || s.length() < 1) {
    		return false;
    	}
    	
    	Boolean result = memo.get(s);
    	if (result != null){
    		return result;
    	}
    	
    	if (dict.contains(s)) {
    		return true;
    	}
    	
    	boolean isBreaks = false;
    	for (int i = 1; i < s.length(); i++) {
			String left = s.substring(0, i);
			boolean isBreaksLeft = canBeSegmented(left, dict, memo);
			memo.put(left, isBreaksLeft);
			if (!isBreaksLeft) {
				continue;
			}
			String right = s.substring(i, s.length());
			boolean isBreaksRight = canBeSegmented(right, dict, memo);
			memo.put(right, isBreaksRight);
			if (isBreaksLeft && isBreaksRight) {
				isBreaks = true;
    			break;
    		}
    	}
        return isBreaks;
	}
    
    private static String prepare(String s) {
    	if (s == null){
    		return s;
    	}
    	StringBuilder sb = new StringBuilder();
    	for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (!Character.isWhitespace(c)) {
				sb.append(c);
			}
		}
    	return sb.toString();
    }
}